#ifndef TREE_H
#define TREE_H

#include <string>

using namespace std;

class Node {

	public:
                            Node(void);
														~Node(void);
				     Node   *getLft(void) { return lft; }
				     Node   *getRht(void) { return rht; }
				     Node   *getAnc(void) { return anc; }
					  int   getIndex(void) { return index; }
                     bool   getIsLeaf(void) { return isLeaf; }
										bool getIsChildRoot(void) { return isChildRoot; }
										bool getIsSubRoot(void) { return isSubRoot; }
				   string   getName(void) { return name; }
				     bool   getFlag(void) { return flag; }
				   double   getV(void) { return v; }
				     void   setLft(Node *p) { lft = p; }
					 void   setRht(Node *p) { rht = p; }
					 void   setAnc(Node *p) { anc = p; }
					 void   setIndex(int x) { index = x; }
					 void   setIsLeaf(bool x) { isLeaf = x; }
					void		setIsChildRoot(bool x) { isChildRoot = x; }
					void		setIsSubRoot(bool x) {isSubRoot = x; }
					 void   setName(string s) { name = s; }
					 void   setFlag(bool x) { flag = x; }
					 void   setV(double x) { v = x; }
					void initCLS(int nc, int ns);
					void setCls(int i, double x) { cls[i] = x; }
					double *getCls(void) { return cls; }
					double *getClsPtr(int i) { return clsPtr[i]; }
					int getClsLength(void) { return clsLength; }
					
	private:
				     Node   *lft;
				     Node   *rht;
				     Node   *anc;
				      int   index;
					 bool   isLeaf;
					bool isChildRoot;
					bool isSubRoot;
				   string   name;
				     bool   flag;
				   double   v;
					double   *cls;
					double	**clsPtr;
					int clsLength;
};

class Alignment;
class MbRandom;
class Tree {

	public:
                            Tree(Alignment *al, MbRandom *rp, string treeStr);
							~Tree(void);
					  int   getNumTaxa(void) { return numTaxa; }
					  int   getNumNodes(void) { return numNodes; }
				     void   getDownPassSequence(void);
					 Node   *getRoot(void) { return root; }
					 Node   *getDownPassNode(int i) { return downPassSequence[i]; }
					 void   print(void);
					
	private:
					 void   buildTreeFromNewickString(string treeStr);
					 void   buildRandomTree(void);
					  int   dex(Node *p);
					 void   passDn(Node *p, int *x);
					 void   showNodes(Node *p, int indent);
			    Alignment   *alignmentPtr;
				 MbRandom   *ranPtr;
				     Node   *nodes;
				     Node   *root;
					 Node   **downPassSequence;
					  int   numTaxa;
					  int   numNodes;
					 bool   isRooted;
					int numChar;
					int numStates;

};

class SubTree {

	public:
			SubTree(Tree *tr, Node *rt, int idx);
			~SubTree(void);
			int   	getNumNodesST(void) { return numNodesST; }
			int			getNumChildRoot(void) { return numChildRoot; }
			SubTree *getAncSubTree(void) { return ancSubTree; }
			int			getIndexST() { return index; }
     	void   	getDownPassSequenceST(void);
			Node   *getSubRoot(void) { return subRoot; }
		 	Node   *getDownPassNodeST(int i) { return downPassSequenceST[i]; }
			double *getClsST(void);
			double **getClsPtrST(double *CST);
			void	setClsST(double *CST);
			void	setAncSubTree(SubTree *st) { ancSubTree = st; }
			int		numChildRoot;

	private:
			int 	numNodesST;
			int		index;
			void  passDnST(Node *p, int *x);
			void  setNumNodesST(Node *sr, int *nNST);
	   	Node   *subRoot;
			Node   **downPassSequenceST;
			SubTree *ancSubTree;
			double *clsST;
			double **clsPtrST;

};

class Queue {
	
	public:
		Queue(int numST);
		~Queue(void);
		void  completeSubTree(SubTree *st);
		void	enqueue(SubTree *st);
		SubTree	*dequeue(void);
		
	private:
		int queueStart;
		int queueEnd;
		SubTree **nextQueue;
		
};

#endif
